package com.yuqian.JavaSe.leetcode.easy;

/**
 * 给定一棵二叉搜索树（BST），寻找BST中两个给定节点的最近公共祖先（LCA）。

根据维基百科对LCA的定义：“节点v与w的最近公共祖先是树T上同时拥有v与w作为后继的最低节点（我们允许将一个节点当做其本身的后继）”

例如，题目描述的样例中，节点2和8的最近公共祖先（LCA）是6。另一个例子，节点2和4的LCA是2，因为根据LCA的定义，一个节点可以是其本身的后继。
 * @author yuqian
 *
 */
public class LowestCommonAncestorofaBinarySearchTree {
	 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
	        if(p.val>q.val){
	        	return lowestCommonAncestor(root,q,p);
	        }
	        if(p.val<=root.val&&q.val>=root.val){
	        	return root;
	        }else{
	        	if(q.val<root.val){
	        		return lowestCommonAncestor(root.left,p,q); 
	        	}else{
	        		return lowestCommonAncestor(root.right,p,q); 
	        	}
	        }
	    }
}
 class TreeNode {
	      int val;
	      TreeNode left;
	      TreeNode right;
	      TreeNode(int x) { val = x; }
	  }
